草庐IT

AtCoder Beginner Contest 252

全部标签

AtCoder Beginner Contest 252

ExK-thBeautifulNecklace题意有N个石头,每个石头有不同的颜色和价值颜色一共有C种,每种颜色至少存在一个石头可以选择一些石头串成一条项链,项链的价值是所有石头价值的异或和从N个石头中选择C个石头串一串项链,要求每个石头的颜色都不同问所有的串法中,价值第K大的项链的价值是多少分析C的最大值是70,假设每个颜色的石头都有2个或3个,那么可选的方案最大值为\(2^{35}\)或\(3^{22}*4\)所以暴力枚举不可取可以进行meet-in-the-middle处理,石头个数为C的项链可以由2串石头个数为C/2的项链拼接得到假设前一串项链为a,后一串项链为b,从a中选择一串项链x
12